package training_camp.day6.leetcode18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int length = nums.length;
        Arrays.sort(nums);
        HashSet<List<Integer>> set = new HashSet<>();
        for (int i = 0; i < length; i++) {
            for (int j = i+1; j < length; j++) {
                int left = j + 1;
                int right = length - 1;
                while (left < right) {
                    if ((long )nums[i] + nums[j] + nums[left] + nums[right] == target) {
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        left++;
                        right--;
                        set.add(list);
                    } else if ((long)nums[i] + nums[j] + nums[left] + nums[right] > target) {
                        right--;
                    } else {
                        left++;
                    }
                }
            }
        }
        List<List<Integer>> ans = new ArrayList<>();
        set.stream().forEach(list -> ans.add(list));
        return ans;
    }

    public static void main(String[] args) {
        int[] ints = {2, 2, 2, 2};
        int target = 8;
        Solution solution = new Solution();
        solution.fourSum(ints,8);
    }
}